package main

import "sort"

type multiKeyMap map[int]map[int]int

func (m multiKeyMap) get(k0 int, k1 int) (int, bool) {
	e1, ok := m[k0]
	if !ok {
		return 0, false
	}
	v, ok := e1[k1]
	return v, ok
}

func (m multiKeyMap) put(k0 int, k1 int, val int) {
	e1, ok := m[k0]
	if !ok {
		e1 = make(map[int]int)
		m[k0] = e1
	}
	e1[k1] = val
}

func threeSum(nums []int) [][]int {
	result := make([][]int, 0)
	m := make(map[int]int) // val -> index
	resultMap := make(multiKeyMap)
	for i, v := range nums {
		m[v] = i
	}
	size := len(nums)
	for i := 0; i < size; i++ {
		for j := i + 1; j < size; j++ {
			val := -nums[i] - nums[j]
			k, ok := m[val]
			if ok && k > i && k > j {
				item := []int{nums[i], nums[j], val}
				sort.Ints(item)
				// whether result exists
				val3, ok := resultMap.get(item[0], item[1])
				if !ok || val3 != item[2] { // result not exists
					result = append(result, item)
					resultMap.put(item[0], item[1], item[2])
				}
			}
		}
	}
	return result
}
